{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2025 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# steel"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/contrib/steel.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/contrib/steel.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "#   Copyright 2010 Pierre Schaus pschaus@gmail.com, lperron@google.com\n",
    "#\n",
    "#   Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "#   you may not use this file except in compliance with the License.\n",
    "#   You may obtain a copy of the License at\n",
    "#\n",
    "#       http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "#   Unless required by applicable law or agreed to in writing, software\n",
    "#   distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "#   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "#   See the License for the specific language governing permissions and\n",
    "#   limitations under the License.\n",
    "\n",
    "import argparse\n",
    "from ortools.constraint_solver import pywrapcp\n",
    "\n",
    "parser = argparse.ArgumentParser()\n",
    "parser.add_argument(\n",
    "    '--data',\n",
    "    default='examples/contrib/steel.txt',\n",
    "    help='path to data file')\n",
    "parser.add_argument(\n",
    "    '--time_limit', default=20000, type=int, help='global time limit')\n",
    "\n",
    "#----------------helper for binpacking posting----------------\n",
    "\n",
    "\n",
    "def BinPacking(solver, binvars, weights, loadvars):\n",
    "  \"\"\"post the load constraint on bins.\n",
    "\n",
    "  constraints forall j: loadvars[j] == sum_i (binvars[i] == j) * weights[i])\n",
    "  \"\"\"\n",
    "  pack = solver.Pack(binvars, len(binvars))\n",
    "  pack.AddWeightedSumEqualVarDimension(weights, loadvars)\n",
    "  solver.Add(pack)\n",
    "  solver.Add(solver.SumEquality(loadvars, sum(weights)))\n",
    "\n",
    "\n",
    "#------------------------------data reading-------------------\n",
    "\n",
    "\n",
    "def ReadData(filename):\n",
    "  \"\"\"Read data from <filename>.\"\"\"\n",
    "  f = open(filename)\n",
    "  capacity = [int(nb) for nb in f.readline().split()]\n",
    "  capacity.pop(0)\n",
    "  capacity = [0] + capacity\n",
    "  max_capacity = max(capacity)\n",
    "  nb_colors = int(f.readline())\n",
    "  nb_slabs = int(f.readline())\n",
    "  wc = [[int(j) for j in f.readline().split()] for i in range(nb_slabs)]\n",
    "  weights = [x[0] for x in wc]\n",
    "  colors = [x[1] for x in wc]\n",
    "  loss = [\n",
    "      min([x for x in capacity if x >= c]) - c for c in range(max_capacity + 1)\n",
    "  ]\n",
    "  color_orders = [[o\n",
    "                   for o in range(nb_slabs)\n",
    "                   if colors[o] == c]\n",
    "                  for c in range(1, nb_colors + 1)]\n",
    "  print('Solving steel mill with', nb_slabs, 'slabs')\n",
    "  return (nb_slabs, capacity, max_capacity, weights, colors, loss, color_orders)\n",
    "\n",
    "\n",
    "#------------------dedicated search for this problem-----------\n",
    "\n",
    "\n",
    "class SteelDecisionBuilder(pywrapcp.PyDecisionBuilder):\n",
    "  \"\"\"Dedicated Decision Builder for steel mill slab.\n",
    "\n",
    "  Search for the steel mill slab problem with Dynamic Symmetry\n",
    "  Breaking during search is an adaptation (for binary tree) from the\n",
    "  paper of Pascal Van Hentenryck and Laurent Michel CPAIOR-2008.\n",
    "\n",
    "  The value heuristic comes from the paper\n",
    "  Solving Steel Mill Slab Problems with Constraint-Based Techniques:\n",
    "    CP, LNS, and CBLS,\n",
    "  Schaus et. al. to appear in Constraints 2010\n",
    "  \"\"\"\n",
    "\n",
    "  def __init__(self, x, nb_slabs, weights, losstab, loads):\n",
    "    pywrapcp.PyDecisionBuilder.__init__(self)\n",
    "    self.__x = x\n",
    "    self.__nb_slabs = nb_slabs\n",
    "    self.__weights = weights\n",
    "    self.__losstab = losstab\n",
    "    self.__loads = loads\n",
    "    self.__maxcapa = len(losstab) - 1\n",
    "\n",
    "  def Next(self, solver):\n",
    "    var, weight = self.NextVar()\n",
    "    if var:\n",
    "      v = self.MaxBound()\n",
    "      if v + 1 == var.Min():\n",
    "        # Symmetry breaking. If you need to assign to a new bin,\n",
    "        # select the first one.\n",
    "        solver.Add(var == v + 1)\n",
    "        return self.Next(solver)\n",
    "      else:\n",
    "        # value heuristic (important for difficult problem):\n",
    "        #   try first to place the order in the slab that will induce\n",
    "        #   the least increase of the loss\n",
    "        loads = self.getLoads()\n",
    "        l, v = min((self.__losstab[loads[i] + weight], i)\n",
    "                   for i in range(var.Min(),\n",
    "                                  var.Max() + 1)\n",
    "                   if var.Contains(i) and loads[i] + weight <= self.__maxcapa)\n",
    "        decision = solver.AssignVariableValue(var, v)\n",
    "        return decision\n",
    "    else:\n",
    "      return None\n",
    "\n",
    "  def getLoads(self):\n",
    "    load = [0] * len(self.__loads)\n",
    "    for w, x in zip(self.__weights, self.__x):\n",
    "      if x.Bound():\n",
    "        load[x.Min()] += w\n",
    "    return load\n",
    "\n",
    "  def MaxBound(self):\n",
    "    \"\"\" returns the max value bound to a variable, -1 if no variables bound\"\"\"\n",
    "    return max([-1] + [\n",
    "        self.__x[o].Min()\n",
    "        for o in range(self.__nb_slabs)\n",
    "        if self.__x[o].Bound()\n",
    "    ])\n",
    "\n",
    "  def NextVar(self):\n",
    "    \"\"\" mindom size heuristic with tie break on the weights of orders \"\"\"\n",
    "    res = [(self.__x[o].Size(), -self.__weights[o], self.__x[o])\n",
    "           for o in range(self.__nb_slabs)\n",
    "           if self.__x[o].Size() > 1]\n",
    "    if res:\n",
    "      res.sort()\n",
    "      return res[0][2], -res[0][1]  # returns the order var and its weight\n",
    "    else:\n",
    "      return None, None\n",
    "\n",
    "  def DebugString(self):\n",
    "    return 'SteelMillDecisionBuilder(' + str(self.__x) + ')'\n",
    "\n",
    "\n",
    "def main(args):\n",
    "  #------------------solver and variable declaration-------------\n",
    "  (nb_slabs, capacity, max_capacity, weights, colors, loss, color_orders) =\\\n",
    "      ReadData(args.data)\n",
    "  nb_colors = len(color_orders)\n",
    "  solver = pywrapcp.Solver('Steel Mill Slab')\n",
    "  x = [solver.IntVar(0, nb_slabs - 1, 'x' + str(i)) for i in range(nb_slabs)]\n",
    "  load_vars = [\n",
    "      solver.IntVar(0, max_capacity - 1, 'load_vars' + str(i))\n",
    "      for i in range(nb_slabs)\n",
    "  ]\n",
    "\n",
    "  #-------------------post of the constraints--------------\n",
    "\n",
    "  # Bin Packing.\n",
    "  BinPacking(solver, x, weights, load_vars)\n",
    "  # At most two colors per slab.\n",
    "  for s in range(nb_slabs):\n",
    "    solver.Add(\n",
    "        solver.SumLessOrEqual([\n",
    "            solver.Max([solver.IsEqualCstVar(x[c], s)\n",
    "                        for c in o])\n",
    "            for o in color_orders\n",
    "        ], 2))\n",
    "\n",
    "  #----------------Objective-------------------------------\n",
    "\n",
    "  objective_var = \\\n",
    "      solver.Sum([load_vars[s].IndexOf(loss) for s in range(nb_slabs)]).Var()\n",
    "  objective = solver.Minimize(objective_var, 1)\n",
    "\n",
    "  #------------start the search and optimization-----------\n",
    "\n",
    "  db = SteelDecisionBuilder(x, nb_slabs, weights, loss, load_vars)\n",
    "  search_log = solver.SearchLog(100000, objective_var)\n",
    "  global_limit = solver.TimeLimit(args.time_limit)\n",
    "  solver.NewSearch(db, [objective, search_log, global_limit])\n",
    "  while solver.NextSolution():\n",
    "    print('Objective:', objective_var.Value(),\\\n",
    "        'check:', sum(loss[load_vars[s].Min()] for s in range(nb_slabs)))\n",
    "  solver.EndSearch()\n",
    "\n",
    "\n",
    "main(parser.parse_args())\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
